0%

【算法导论】图的广度优先搜索遍历（BFS）

发表于 更新于
本文字数： 4.9k 阅读时长 ≈ 7 分钟

​ 图的存储方法：邻接矩阵、邻接表

​ 例如：有一个图如下所示(该图也作为程序的实例)：

图1

则上图用邻接矩阵可以表示为：

图2

用邻接表可以表示如下：

图3

邻接矩阵可以很容易的用二维数组表示，下面主要看看怎样构成邻接表：

​ 邻接表存储方法是一种顺序存储与链式存储相结合的存储方法。在这种方法中，只考虑非零元素，所以在图中的顶点很多而边很少时，可以节省存储空间。
​ 邻接表存储结构由两部分组成：对于每个顶点$v_i$, 使用一个具有两个域的结构体数组来存储，这个数组称为顶点表。其中一个域称为顶点域(vertex)，用来存放顶点本身的数据信息；而另一个域称为指针域(link)，用来存放依附于该顶点的边所组成的单链表的表头结点的存储位置。邻接于$v_i$的顶点$v_j$链接成的单链表称为$v_i$的邻接链表。邻接链表中的每个结点由两个域构成：一是邻接点域(adjvex)，用来存放与$v_i$相邻接的顶点$v_j$的序号$j$ (可以是顶点$v_j$在顶点表中所占数组单元的下标)； 其二是链域(next)，用来将邻接链表中的结点链接在一起。具体的程序实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void CreateAdjTable(vexnode ga[N],int e)//创建邻接表
{
	int i,j,k;
	edgenode *s;
	printf("\n输入顶点的内容：");
	for(i=0;i<N;i++)
	{
		ga[i].vertex=getchar();//读入顶点的内容
		
		ga[i].link=NULL;//初始化
	}
	printf("\n");
	for(k=0;k<e;k++)
	{
		printf("输入边的两个顶点的序号:");
		scanf("%d%d",&i,&j);//读入边的两个顶点的序号
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=j;
		s->next=ga[i].link;
		ga[i].link=s;

		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=i;
		s->next=ga[j].link;
		ga[j].link=s;

	}
}

广度优先搜索遍历（BFS）:

​ 图的广度优先搜索遍历类似于树的按层次遍历。在假设初始状态是图中所有顶点都未被访问的条件下，这种方法从图中某一顶点$v_i$出发，先访问$v_i$，然后访问$v_i$的邻接点$v_j$。在所有的$v_j$都被访问之后，再访问$v_j$的邻接点$v_k$，依次类推，直到图中所有和初始出发点$v_i$有路径相通的顶点都被访问为止。若图是非连通的，则选择一个未曾被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。
​ 在这种方法的遍历过程中，先被访问的顶点，其邻接点也先被访问，具有先进先出的特性，所以可以使用一个队列来保存已访问过的顶点，以确定对访问过的顶点的邻接点的访问次序。为了避免重复访问一个顶点，也使用了一个辅助数组visited[n]来标记顶点的访问情况。下面分别给出以邻接矩阵和邻接表为存储结构时的广度优先搜索遍历算法BFS_matrix和BFS_AdjTable:

具体程序实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include<stdio.h>
#include<stdlib.h>
#define N 5

//邻接矩阵存储法
typedef struct 
{
	char vexs[N];//顶点数组
	int arcs[N][N];
}graph;

//邻接表存储法
typedef struct Node
{
	int adjvex;
	struct Node *next;

}edgenode;

typedef struct
{
	char vertex;
	edgenode *link;
}vexnode;

//队列操作
typedef struct node
{
	int data;
	struct node *next;
}linklist;

typedef struct
{
	linklist *front,*rear;
}linkqueue;

void SetNull(linkqueue *q)//队列置空
{
	q->front=(linklist *)malloc(sizeof(linklist));
	q->front->next=NULL;
	q->rear=q->front;
}

int Empty(linkqueue *q)
{
	if(q->front==q->rear)
		return 1;
	else 
		return 0;
}

int Front(linkqueue *q)//取队头元素
{
	if(Empty(q))
	{
		printf("queue is empty!");
		return -1;
	}
	else
		return q->front->next->data;
}

void ENqueue(linkqueue *q,int x)//入队
{
	linklist * newnode=(linklist *)malloc(sizeof(linklist));
    q->rear->next=newnode;
	q->rear=newnode;
	q->rear->data=x;
	q->rear->next=NULL;
	
}

int DEqueue(linkqueue *q)//出队
{
	int temp;
	linklist *s;
	if(Empty(q))
	{
		printf("queue is empty!");
		return -1;
	}
	else
	{
		s=q->front->next;
		if(s->next==NULL)
		{
			q->front->next=NULL;
			q->rear=q->front;
		}
		else
			q->front->next=s->next;
		temp=s->data;
		return temp;
	}
}

void BFS_matrix(graph g,int k,int visited[N])//图按照邻接矩阵存储时的广度优先遍历
{
	int i=0;
	linkqueue q;
	SetNull(&q);
	printf("%c\n",g.vexs[k]);
	visited[k]=1;
	ENqueue(&q,k);
	while(!Empty(&q))
	{
		i=DEqueue(&q);
		for(int j=0;j<N;j++)
		{
			if(g.arcs[i][j]==1&&visited[j]!=1)
			{
				printf("%c\n",g.vexs[j]);
				visited[j]=1;
				ENqueue(&q,j);
			}
		}
	}
}

void CreateAdjTable(vexnode ga[N],int e)//创建邻接表
{
	int i,j,k;
	edgenode *s;
	printf("\n输入顶点的内容：");
	for(i=0;i<N;i++)
	{
		ga[i].vertex=getchar();//读入顶点的内容
		
		ga[i].link=NULL;//初始化
	}
	printf("\n");
	for(k=0;k<e;k++)
	{
		printf("输入边的两个顶点的序号:");
		scanf("%d%d",&i,&j);//读入边的两个顶点的序号
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=j;
		s->next=ga[i].link;
		ga[i].link=s;

		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=i;
		s->next=ga[j].link;
		ga[j].link=s;

	}
}

void BFS_AdjTable(vexnode ga[],int k,int visited[N])//图按照邻接表存储时的广度优先遍历
{
	int i=0;
	edgenode *p;
	linkqueue q;
	SetNull(&q);
	printf("%c\n",ga[k].vertex);
	visited[k]=1;//标记是否被访问过
	ENqueue(&q,k);//入队
	while(!Empty(&q))
	{
		i=DEqueue(&q);
		p=ga[i].link;
		while(p!=NULL)
		{
			if(visited[p->adjvex]!=1)
			{
				printf("%c\n",ga[p->adjvex].vertex);
				visited[p->adjvex]=1;
				ENqueue(&q,p->adjvex);
			}
			p=p->next;
		}
	}
}


void main()
{
	graph g;
	vexnode ga[N];
	int visited[5]={0};
	int visited1[5]={0};
	g.vexs[0]='A';
	g.vexs[1]='B';
	g.vexs[2]='C';
	g.vexs[3]='D';
	g.vexs[4]='E';
	int a[5][5]={{0,1,0,1,1},{ 1,0,1,0,1},{ 0,1,0,0,0},{ 1,0,0,0,0},{ 1,1,0,0,0}};
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			g.arcs[i][j]=a[i][j];
	printf("图按照邻接矩阵存储时的广度优先遍历：\n");
	BFS_matrix(g,0,visited);
	CreateAdjTable(ga,5);
	printf("图按照邻接表存储时的广度优先遍历：\n");
	BFS_AdjTable(ga,0,visited1);
}

其结果如下图：

图4

从上面可以看出，两种方式的结果不同，但都是正确的，因为这与邻接点访问的顺序有关。

坚持原创技术分享，您的支持将鼓励我继续创作！